package algorithmic_data_structure.堆与堆排序.mycode

import utils.NumberUtils

/**
 * @author :
 * @date : 2022/4/21 18:31
 */
fun main() {
    //最小堆
    val heapGreater = HeapGreater<Int> { o1, o2 -> o1 - o2 }
    heapGreater.push(1)
    heapGreater.push(6)
    heapGreater.push(2)
    heapGreater.push(5)
    heapGreater.push(4)
    heapGreater.push(3)
//    val t = heapGreater.deepCopy()
//    t.popAllAndPrint()

    heapGreater.getAllElements().forEach { print("$it ") };println()
    heapGreater.remove(2)
    heapGreater.getAllElements().forEach { print("$it ") };println()
    heapGreater.remove(4)
    heapGreater.getAllElements().forEach { print("$it ") };println()
    heapGreater.push(0)
    heapGreater.getAllElements().forEach { print("$it ") };println()
}

/**
 * 加强堆
 * 普通的堆是无法记录堆中元素的位置的，而且如果堆中元素发生变化，对其在堆中的位置进行修改时间复杂度也会很高
 */
class HeapGreater<T> constructor(private val c: Comparator<T>) {

    private val heap: ArrayList<T> = ArrayList()
    private val indexMap: HashMap<T, Int> = HashMap()
    private var heapSize: Int = 0
    private val comparator: Comparator<T> = c

    fun isEmpty(): Boolean {
        return heapSize == 0
    }

    fun size(): Int {
        return heapSize
    }

    fun contains(obj: T): Boolean {
        return indexMap.containsKey(obj)
    }

    /**
     * 有可能数组为空报错
     */
    fun peek(): T {
        return heap[0]
    }

    fun push(obj: T) {
        heap.add(obj)
        indexMap[obj] = heapSize
        heapInsert(heapSize++)
    }

    fun pop(): T {
        if (heapSize == 0) {
            throw RuntimeException("当前堆为空，无法弹值")
        }
        val res = heap[0]
        indexMap[heap[heapSize - 1]] = 0
        NumberUtils.swap(heap, 0, heapSize - 1)
        heap.removeAt(--heapSize)
        indexMap.remove(res)
        heapify(0)
        return res
    }

    fun remove(obj: T) {
        if (heapSize == 0) {
            throw RuntimeException("当前堆为空，无法删除元素")
        }
        if (!contains(obj)) {
            throw RuntimeException("当前堆中并没有要删除的元素")
        }
        //取出堆中末尾的元素与要删除的元素进行替换
        val replaceValue = heap[heapSize - 1]
        val removeIndex = indexMap[obj]!!
        indexMap.remove(obj)
        heap.removeAt(--heapSize)
        //如果要删除的元素就是堆中末尾元素，就无需其他操作了
        if (replaceValue != obj) {
            heap[removeIndex] = replaceValue
            indexMap[replaceValue] = removeIndex
            resign(removeIndex)
        }
    }

    /**
     * 堆中元素修改之后需要堆受影响的位置重新进行校正
     */
    private fun resign(index: Int) {
        heapify(index)
        heapInsert(index)
    }

    // 请返回堆上的所有元素
    fun getAllElements(): List<T> {
        val ans = ArrayList<T>()
        for (c in heap) {
            ans.add(c)
        }
        return ans
    }

    fun popAllAndPrint() {
        while (heapSize > 0) {
            print("${pop()} ,")
        }
        println()
    }

    private fun heapify(index: Int) {
        var index = index
        var left = index * 2 + 1
        while (left < heapSize) {
            var bestSon =
                if (left + 1 < heapSize && comparator.compare(heap[left + 1], heap[left]) < 0) {
                    left + 1
                } else {
                    left
                }
            if (comparator.compare(heap[index], heap[bestSon]) < 0) {
                break
            }
            indexMap[heap[bestSon]] = index
            indexMap[heap[index]] = bestSon
            NumberUtils.swap(heap, index, bestSon)
            index = bestSon
            left = index * 2 + 1
        }
    }

    private fun heapInsert(heapSize: Int) {
        var index = heapSize
        //如果比较结果为-1说明第一个参数需要排在前面，所以将当前元素与父节点进行替换
        while (comparator.compare(heap[index], heap[(index - 1) / 2]) < 0) {
            //记录元素下标的哈希表也需要修改
            indexMap[heap[index]] = (index - 1) / 2
            indexMap[heap[(index - 1) / 2]] = index

            NumberUtils.swap(heap, index, (index - 1) / 2)
            index = (index - 1) / 2
        }
    }
}